package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //珠宝的最高价值
    public int jewelleryValue(int[][] frame) {
        int n = frame.length;
        int m = frame[0].length;
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <=n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])+frame[i-1][j-1];
            }
        }
        return dp[n][m];
    }

    //不同路径 2
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1) return 0;
        int[][] dp = new int[n+1][m+1];
        dp[1][1] = 1;
        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < m+1; j++) {
                if(i==1 && j==1) continue;
                if(obstacleGrid[i-1][j-1]!=1){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[n][m];
    }

    //解码方法
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n];
        if(s.charAt(0)=='0') return 0;
        else {
            dp[0] = 1;
        }
        if(n==1) return dp[0];
        int a = 0,b = 0,sum = 0;
        a = (s.charAt(0)-'0')*10;
        b = s.charAt(1)-'0';
        sum = a+b;
        if(sum>=1 && sum<=26) {
            if(s.charAt(1)=='0'){
                dp[1] = 1;
            }else{
                dp[1] = 2;
            }
        }else {
            if(s.charAt(1)=='0'){
                dp[1] = 0;
            }else{
                dp[1] = 1;
            }
        }
        for (int i = 2; i < n; i++) {
            int key1 = 0;int key2 = 0;
            char ch = s.charAt(i);
            a = (s.charAt(i-1)-'0')*10;
            b = ch-'0';
            sum = a+b;
            if(ch=='0'){
                if(sum>=1 && sum<=26 && s.charAt(i-1)!='0') key2 = dp[i-2];
            }else {
                key1 = dp[i-1];
                if(sum>=1 && sum<=26 && s.charAt(i-1)!='0') key2 = dp[i-2];
            }
            dp[i] = key1+key2;
        }
        return dp[n-1];
    }
}
















